package zuo.highLevel_1;

/**
 * @Author: Forx
 * @Data: 2021/7/4
 * @Desc: Algorithm - zuo.highLevel_1
 * @Version: v1.0
 */

import java.util.HashMap;

/**
 * 给定一个数组，求如果排序之后，相邻两数的最大差值。要求时间复杂度O(N),且要
 * 求不能用非基于比较的排序。(桶排序,计数排序...)
 *
 * 还是用桶,但是不是桶排序,先遍历获得最大最小,然后将数组元素放桶里面
 * 每个桶只保存在这个桶中的最大值max最小值min
 * 假定数组长度为l,每个桶的gap是(max-min)/(l+1)
 * 但是妙就妙在划分成n+1个桶,那么这样就必然会出现一个空桶,这样就能排除掉同一个桶内出现gap最大的情况
 * 因为空桶两边的gap必然一定大于桶一个桶内的元素gap,于是就靠这个空桶滤除掉了许多可能解
 *
 * */
class MaxDiff{

}
/**
 * 给出n个数字a_1,...,a_n,问最多有多少不重叠的非空区间，使得每个区间内数字的
 * xor都等于0。
 * 假设已经知道0-i-1位置上最多有k个空间,看i位置
 * 若i为0 那么最多就是k+1
 * 若i不为0 如果上一个区间内最后一个异或不为0的区间的末尾是i-1的话,那就用i于其异或看是不是0
 * 若是那就是k+1,不是就是k
 *
 * */
class NoRepeatGapWithXOR_0{
    public int mostEOR(int[] arr){
        int xor =  0;
        int[] dp = new int[arr.length];
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        for (int i = 0; i < arr.length; i++) {
            xor^=arr[i];
            if(map.containsKey(xor)){
                int pre = map.get(xor);
                dp[i] = pre==-1?1:(dp[pre]+1);
            }
            if(i>0){
                dp[i] = Math.max(dp[i-1],dp[i]);
            }
            map.put(xor,i);

        }

        return dp[arr.length-1];
    }
}
/**
 * 现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为纪念币，
 * 每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值？
 * */
class HowManyMethods{

}
/**
 * 两个有序数组从小到大,找到总体第K小的
 * 数P465-P470
 * 方法1:分别指向ARR1,ARR2的两个指针,谁小谁走,直到第K个,时间复杂度O(K)
 * 方法2:在数组1中,使用2分找中位数mid,再在数组2中用二分找到小于mid的数的数量
 *      如果发现小于mid的数量大于k,那么就在mid-end中在试,小于同理
 *      时间复杂度O(loglen1 * loglen2)
 * 方法3:书本上的时间复杂度是O(log(min(len1,len2)))
 * */



public class HL1 {
}
